|
In the mathematical field of graph theory, a convex bipartite graph is a bipartite graph with specific properties. A bipartite graph, (''U'' ∪ ''V'', ''E''), is said to be convex over the vertex set ''U'' if ''U'' can be enumerated such that for all ''v'' ∈ ''V'' the vertices adjacent to ''v'' are consecutive. Convexity over ''V'' is defined analogously. A bipartite graph (''U'' ∪ ''V'', ''E'') that is convex over both ''U'' and ''V'' is said to be biconvex or doubly convex. ==Formal definition== Let ''G'' = (''U'' ∪ ''V'', ''E'') be a bipartite graph, i.e, the vertex set is ''U'' ∪ ''V'' where ''U'' ∩ ''V'' = ∅. Let ''N''''G''(''v'') denote the neighborhood of a vertex ''v'' ∈ ''V''. The graph ''G'' is convex over ''U'' if and only if there exists a bijective mapping, ''f'': ''U'' → , such that for all ''v'' ∈ ''V'', for any two vertices ''x'',''y'' ∈ ''N''''G''(''v'') ⊆ ''U'' there does not exist a ''z'' ∉ ''N''''G''(''v'') such that ''f''(''x'') < ''f''(''z'') < ''f''(''y''). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「convex bipartite graph」の詳細全文を読む スポンサード リンク
|